class Solution {
public:
    set<string> results;
    string path;
    bool used[10] = {false};

    vector<string> Permutation(string str) {
        dfs(str, 0);
        vector<string> ret(results.begin(), results.end());

        return ret;
    }

    void dfs(string& str, int start)
    {
        if(path.size() == str.size())
        {
            results.insert(path);
            return;
        }

        for(int i = 0; i < str.size(); ++i)
        {
            if(used[i]) continue;
            if(i > 0 && str[i] == str[i-1] && !used[i-1])
                continue;
            
            if(!used[i])
            {
                used[i] = true;
                path += str[i];
                dfs(str, i+1);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};


class Solution {
public:
    vector<string> results;
    
    vector<string> generateParenthesis(int n) {
        dfs("", 0, 0, n);
        return results;
    }

    void dfs(string path, int leftCount, int rightCount, int n)
    {
        if(path.size() == 2*n)
        {
            results.push_back(path);
            return;
        }
        if(leftCount < n)
        {
            dfs(path+"(", leftCount+1, rightCount, n);
        }
        if(rightCount < leftCount)
        {
            dfs(path+")", leftCount, rightCount+1, n);
        }
    }
};
